\section{Preliminaries} \label{sec:prelim}

For any undirected unweighted graph $G$, let $V(G)$ and $E(G)$ be the set of nodes and edges in $G$, respectively.  
%Throughout, we let $n=|V(G)|$ and $m=|E(G)|$. 
The {\em density of $G$}, denoted by $\sigma(G)$, is defined by 
$$\sigma(G)=|E(G)|/|V(G)|.$$ 
The densest subgraph of $G$ is the subgraph of $G$ with highest density. We use $\sigma^*(G)$ to denote density of the densest subgraph of $G$, i.e. 
$$\sigma^*(G)=\max_{H\subseteq G} \sigma(H)$$ 
where the maximization is over all subgraphs $H$ of $G$. For any numbers $\alpha\geq 1$, $\sigma'$, and graph $G$, we say that $\sigma'$ is an {\em $\alpha$-approximate value} of $\sigma^*(G)$ if
%a subgraph $H$ such that 
%
%an algorithm for computing the densest subgraph is {\em $\alpha$-approximation} if it outputs a value $\sigma'$ such that 
%a subgraph $H$ such that 
$$ \sigma^*(G)/\alpha \leq \sigma' \leq \sigma^*(G).$$
%
An {\em incremental $\alpha$-approximation} algorithm for the densest subgraph problem
%is to maintain an approximate value of $\sigma^*(G)$ for an input graph $G$ undergoing edge insertions. In particular, 
is a data structure that maintains an approximate value of $\sigma^*(G)$ for an undirected unweighted graph $G$ under a sequence of update and query operations. In particular, it supports the following operations.

\begin{itemize}
	\item {\sc Initialize}($G$): intialize the data structure with input graph $G$,
	\item {\sc Update}($E'$): insert edges in the set of edges $E'$ to the graph, and
	\item {\sc Query}: return an $\alpha$-approximate value of $\sigma^*(G)$.
\end{itemize} 


Define the {\em initialization time}, {\em update time}, and {\em query time} to be the time to process the {\sc Initialize}($G$), {\sc Update}($E'$), and {\sc Query} operations, respectively. 
%We consider two types of update time: 
%
%whose density is approximately close to the value of $\sigma^*(G)$ under edge insertions. In particular, we want to maintain the value of $\sigma^*(G)$ after inserting a set $E'$ of edges into $G$. 
% 
%
%All algorithms in this paper have a query time of $O(1)$ and thus we wil
%
We say that an algorithm has a {\em worst-case update time} of $\tau$ if each update operation takes at most $\tau$ time. 
%
%after each insertion it can compute a new approximate value of $\sigma^*(G)$ in $\tau$ time. 
%
We say that an algorithm has a {\em total update time} of $\tau'$ if the total time the algorithm uses to process all update operations is at most $\tau'$. If an algorithm has $\tau'$ total update time over $p$ update operations, then it has $\tau'/p$ {\em amortized update time}. 
%
We will analyze the running time as a function of three pameters $n$, $m$ and $p$ where we let $n$ be the number of nodes in the graph after all update operations, $m$ be the number of edges in the graph after all update operations, and $p$ be the total number of update operations. Note that while the most interesting case is when $m=p$, i.e. there is one edge inserted in each update, we will analyze our algorithms in a more general case where there may be many edges inserted in the same update operation to show the full potential of our result.

%Note that $m\geq p$, and there may be many edges inserted in the same update operation.


 
 
\section{Algorithm}\label{sec:algo}

In this section we develop an algorithm for approximating the densest subgraph under edge insertions. Recall that in the static setting we can get a $2$-approximation in $O(m)$-time using the algorithm of Charikar \cite{Charikar00}. Unfortunately, running this algorithm over $p$ insertions will cost $O(mp)$ total update time which could be expensive when $p$ is large (e.g. $p=m$). We show that we can get very close to $O(m)$ time if we are satisfied with a larger approximation guarantee:


%
%\begin{theorem}\label{thm:near linear algo}
%For any $k\geq 1$, there is an algorithm that can incrementally maintain a $(2k)$-approximation of the densest subgraph in $O(m^{1/k})$ update time in the worst case.
%\end{theorem}

\begin{theorem}\label{thm:near linear algo}
For any $k\geq 1$ and $p$, there is an algorithm that can incrementally maintain a $(2k)$-approximate value of the densest subgraph under $p$ updates in $O(mkp^{1/k})$ total update time. This algorithm has $O(1)$ query time and linear initialization time (i.e.  {\sc Initialize}($G$) takes $O(|E(G)|)$ time). 
\end{theorem}

\noindent{\em Remark.} 
%We note that although we define the problem as maintaining the approximate value of $\sigma^*(G)$, all our algorithms can output a subgraph $H$ such that $\sigma(H)=\sigma'$ as well.  
We note that although we require the {\sc Query} operation to return only an approximate value $\sigma'$ of $\sigma^*(G)$, our algorithm can actually return the subgraph $H$ with density $\sigma'$ in linear (i.e. $O(|E(H)|)$ time). \\

To see the power of our new algorithm, consider, for example, the situation where edges are gradually added to the graph one at a time (thus $p=m$). Naively running Charikar's algorithm every time will take $O(m^2)$ total update time while our algorithm needs only $O(km^{1+1/k})$ total update time. In particular, when we set $k=\log n$, we get a total update time of only $O(m\log^2 n)$ (thus  $O(\log^2 n)$ amortized update time). 


%We note that in fact our technique can be generalized to turn any static algorithm for any problem into an incremental one. We will state and proof this generalization in \Cref{sec:generalization}. 


%\subsection{The Simplest Case}\label{sec:simplest algo}

%To explain the key ideas of the algorithm, we first prove \Cref{thm:near linear algo} with an assumption that the number of updates ($q$) is known to the algorithm from the beginning. We will show how to remove this assumption later. 
%
%there are $m$ updates, where there is exactly one new edge in each update. Moreover, we assume that the algorithm knows the number of edges from the start. 
%



We present our algorithms in the following subsections. In \Cref{sec:algo offline}, we present an algorithm with an assumption that $m$ and $p$ are known. This algorithm is easier to analyze and is useful in the ``offline'' setting when the whole input dynamic graph is already available (e.g. when we want to track the densest subgraph over a period of time in the past). In \Cref{sec:algo online} we extend this algorithm to the ``online'' case where $m$ and $p$ are unknown. Finally, in \Cref{sec:worst case} we note how to achieve a worst case update time. 


\subsection{Algorithm when $m$ and $p$ are known}\label{sec:algo offline}


\begin{algorithm}
	\caption{{\sc Incremental-Densest-Subgraph}($G$, $k$, $n$, $m$, $p$)}\label{alg:simple}
	
	{\bf Input:}  The initial graph $G=(V, E)$, an integer $k\geq 1$, the total number of nodes $n$, the total number of edges $m$, and the total number of update operations $p$. 
	
	{\bf Maintain:} A $(2k)$-approximate value of $\sigma^*(G)$.
	
	\medskip{\sc Initialize}($G$):
	\noindent
	\begin{algorithmic}[1]
		\State For all $1\leq i\leq k$, let $E_1=E_2=\ldots=E_{k-1} = \emptyset$,  and $\sigma_1=\sigma_2=\ldots=\sigma_{k-1}=0$. 
		\State Let $E_k=E$ and compute $\sigma_k$ as the $2$-approximate value of $\sigma(G)$ using {\sc StaticAlgo}.
		\algstore{myalg}
	\end{algorithmic}
	
	%\smallskip{\bf Update:} When edges in $E'$ are added, do the following.
	\medskip {\sc Update}($E'$):
	\begin{algorithmic}
		\algrestore{myalg}
		%\State Let $q$ be a power of two (i.e. $q=2^i$ for some $i$) such that $q/2<p\leq q$. 
		%\State $E_1=E_1\cup E'$. 
		\State Let $i$ be the smallest number such that $|E'\cup E_1\cup E_2\cup \ldots \cup E_i|\leq \frac{m}{p^{1-i/k}}$. \label{line:def i}
		\State $E_i=E'\cup E_1\cup E_2\cup \ldots \cup E_i$. \label{line:simple algo move edges}
		\State Compute $\sigma_{i}$ as the $2$-approximate value of $\sigma(G_{i})$ using {\sc StaticAlgo}($G_i$), where $G_{i}=(V, E_{i})$. \label{line:simple recompute sigma_i}
		\State $E_1= E_2= \ldots = E_{i-1}=\emptyset$ and $\sigma_1=\sigma_2=\ldots \sigma_{i-1}=0$.\danupon{Note that this is not necessary in the real implementation as previous values of $\sigma_i$ might help.}
		\algstore{myalg2}
	\end{algorithmic}
	
	\medskip{\sc Query}:
	\begin{algorithmic}
		\algrestore{myalg2}
		\State Output $\max_{i=1}^k \sigma_i$ as the approximate value of $\sigma^*(G)$. 
	\end{algorithmic}
\end{algorithm}

Our algorithm is described in \Cref{alg:simple}. It runs the static $2$-approximation $O(m)$-time algorithm of Charikar \cite{Charikar00}, denoted by {\sc StaticAlgo}, as a subroutine. 
%
It maintains a partition of edges in $G$ into $k$ sets denoted by $E_1, E_2, \ldots, E_k$ and computes $\sigma_i$ as the $2$-approximate value of $\sigma^*(G_i)$ in each subgraph $G_i=(V, E_i)$.  It answers the query operation by outputting $\max_{i=1}^k \sigma_i$. As will be shown in the approximation analysis below, this easily gives a $(2k)$-approximate value of $\sigma^*(G)$. 
%
When a set of new edges, denoted by $E'$, is inserted into $G$, it has to put edges in $E'$ to some $E_i$. In order to achieve the claimed update time, the crucial idea is to define $i$ as the smallest value such that 
$$|E'\cup E_1\cup \ldots \cup E_i|\leq \frac{m}{p^{1-i/k}},$$ 
%
%where $m'$ and $q'$ are the current number of edges and insertions, respectively. 
%
The algorithm will move all edges in $E'\cup E_1\cup \ldots \cup E_{i-1}$ to $E_i$ and recompute the value $\sigma_i$. The intuition behind this definition of $i$ is that we can bound the cost of recomputing $\sigma_i$ by $|E'\cup E_1\cup \ldots \cup E_i|\leq \frac{m}{p^{1-i/k}}$. Moreover, we can bound the number of times we have to recompute $\sigma_i$ since this happens only when  $|E'\cup E_1\cup \ldots \cup E_{i-1}|>\frac{m}{p^{1-(i-1)/k}}$. (See the time analysis below for detail.)

%It then uses $\max_{i=1}^k \sigma_i$ as the approximate value of $\sigma^*(G)$. 


%
%Our algorithm maintains a partition of edges into $k$ sets, denoted by $E_1, E_2, \ldots E_k$, and the corresponding subgraphs $G_1, \ldots, G_k$ of $G$ where $G_i=(V, E_i)$. It answers the query operation by outputting the $2$-approximate value of $\max_{i=1}^k \sigma^*(G_i)$  (which can be computed by Charikar's linear-time $2$-approximation algorithm \cite{Charikar00}). We will show in a moment that this easily gives a $2$-approximate value to $\sigma^*(G)$. 
%%
%To bound the total update time, we maintain the following invariant. 
%$$|E_i|\leq \frac{m}{p^{1-i/k}}.$$



\paragraph{Approximation Guarantee Analysis}
%\label{sec:approx analysis}
%
We rely on the following simple property.  

\begin{lemma}[Subadditivity]\label{thm:subadditivity}
	For any graphs $G_1=(V, E_1)$ and $G_2=(V, E_2)$, let $G=(V, E_1\cup E_2)$. Then, 
	$$\sigma^*(G)\leq \sigma^*(G_1)+\sigma^*(G_2).$$ 
\end{lemma}
\begin{proof}
	Let $H$ be the densest subgraph of $G$. Let $H_1$ and $H_2$ be the subgraph of $G_1$ and $G_2$, respectively, induced by vertices in $V(H)$. In other words $E(H)=E(H_1)\cup E(H_2)$. Then
	$$\sigma^*(G) = \frac{|E(H)|}{|V(H)|} \leq \frac{|E(H_1)|}{|V(H)|} + \frac{|E(H_2)|}{|V(H)|} \leq \sigma^*(G_1)+\sigma^*(G_2)$$ as claimed. 
\end{proof}

Recall that \Cref{alg:densest subgraph} maintains sets of edges $E_1, \ldots, E_k$ such that $E_1 \cup E_2 \cup \ldots \cup E_k = E$ and $2$-approximate values $\sigma_1, \ldots, \sigma_k$ of $\sigma^*(G_1), \ldots, \sigma^*(G_k)$, respectively. It follows from \Cref{thm:subadditivity} that 
\begin{align*}
\sigma^*(G) &\leq \sigma^*(G_1)+\sigma^*(G_2)+\ldots +\sigma^*(G_k) \\
&\leq 2(\sigma_1+\ldots +\sigma_k)\\
&\leq 2k \max_{i=1}^k \sigma_i,.
\end{align*}
%\[\sigma^*(G)\leq \sigma^*(G_1)+\sigma^*(G_2)+\ldots +\sigma^*(G_k) \leq 2(\sigma_1+\ldots +\sigma_k).\]
%In other words, $\max_{i=1}^k \sigma_i \geq \sigma^*(G)/2k$. 
Thus \Cref{alg:densest subgraph} gives a $(2k)$-approximate value of $\sigma^*(G)$ as claimed.




\paragraph{Time Analysis} We first count the number of times we have to recompute $\sigma_i$ (as in Line~\ref{line:simple recompute sigma_i}) for each $i$. Observe that, by the definition of $i$ in Line~\ref{line:def i}, at the time we recompute $\sigma_i$ in Line~\ref{line:simple recompute sigma_i}, 
$$|E'\cup E_1\cup E_2\cup \ldots \cup E_{i-1}|> \frac{m}{p^{1-(i-1)/k}}$$
%
and after this recomputation we will remove all edges from $E_i$ (i.e. $E_1= E_2= \ldots = E_{i-1}=\emptyset$). Since these removed edges will never appear in $E_1\cup E_2 \cup \ldots E_{i-1}$ again, the number of times we have to recompute each $\sigma_i$ can be bounded by 
$$\frac{m}{|E'\cup E_1\cup E_2\cup \ldots \cup E_{i-1}|} < p^{1-(i-1)/k}.$$
Recall that recomputing $\sigma_i$ (using {\sc StaticAlgo$(G_i)$}) requires  $O(|E(G_i)|)$ time. Thus, the total time we need to recompute each $\sigma_i$ over {\em all} update opertions is
%Thus, for each $i$ the total time we need for {\em all} executions of {\sc StaticAlgo}$(G_i)$  is 
$$O(|E(G_i)|\times p^{1-(i-1)/k}) = O(\frac{m}{p^{1-i/k}}\times p^{1-(i-1)/k}) = O(mp^{1/k})$$
where the first equality is because 
$$|E'\cup E_1\cup E_2\cup \ldots \cup E_i|\leq \frac{m}{p^{1-i/k}}$$ 
by the definition of $i$. 
Summing over all $i$, we have that the total time we need to recompute all $\sigma_i$ over all updates is $O(kmp^{1/k})$. 
%
This also implies the total update time since the time needed to execute other steps of the {\sc Update}($G_i$) opertion is dominated by the time we need to recompute $\sigma_i$ in Line~\ref{line:simple recompute sigma_i}.


\subsection{Algorithm when $m$ and $p$ are unknown}\label{sec:algo online}

\begin{algorithm}
\caption{{\sc Incremental-Densest-Subgraph}($G$, $k$)}\label{alg:densest subgraph}

{\bf Input:}  The initial graph $G=(V, E)$ and an integer $k\geq 1$.

{\bf Maintain:} A $(2k)$-approximate value of $\sigma^*(G)$.

\medskip{\sc Initialize}($G$): Same as \Cref{alg:simple}. Additionally let $p'=0$ and $m'=|E|$.
%\noindent
%\begin{algorithmic}[1]
%\State $p'=0$ and $m'=|E|$.
%\State For all $1\leq i\leq k$, let $E_1=E_2=\ldots=E_{k-1} = \emptyset$,  and $\sigma_1=\sigma_2=\ldots=\sigma_{k-1}=0$. 
%\State Let $E_k=E$ and compute $\sigma_k$ as the $2$-approximate value of $\sigma(G)$ using {\sc StaticAlgo}.
%\algstore{myalg}
%\end{algorithmic}

%\smallskip{\bf Update:} When edges in $E'$ are added, do the following.
\medskip {\sc Update}($E'$):
\begin{algorithmic}[1]
%\algrestore{myalg}
\State $p'=p'+1$ and $m'=m'+|E'|$.
%\State Let $q$ be a power of two (i.e. $q=2^i$ for some $i$) such that $q/2<p\leq q$. 
%\State $E_1=E_1\cup E'$. 
\State Let $i$ be the smallest number such that $|E'\cup E_1\cup E_2\cup \ldots \cup E_i|\leq \frac{m'}{(p')^{1-i/k}}$. \danupon{This might be faster when implemented}
\State $E_i=E'\cup E_1\cup E_2\cup \ldots \cup E_i$. \label{line:move edges}
\State Compute $\sigma_{i}$ as the $2$-approximate value of $\sigma(G_{i})$ using {\sc StaticAlgo}, where $G_{i}=(V, E_{i})$. \label{line:recompute sigma_i}
\State $E_1= E_2= \ldots = E_{i-1}=\emptyset$ and $\sigma_1=\sigma_2=\ldots \sigma_{i-1}=0$.\danupon{Note that this is not necessary in the real implementation as previous values of $\sigma_i$ might help.}
%\algstore{myalg2}
\end{algorithmic}

\medskip
{\sc Query}: Same as \Cref{alg:simple}.

%\medskip{\sc Query}:
%\begin{algorithmic}
%\algrestore{myalg2}
%\State Output $\max_{i=1}^k \sigma_i$ as the approximate value of $\sigma^*(G)$. 
%\end{algorithmic}
\end{algorithm}

We deal with the case where $m$ and $p$ are unknown in an obvious way: we simply replace the values of $m$ and $p$ by $m'$ and $p'$ in our algorithm, where $m'$ and $p'$ are the {\em current} number of edges and updates; see \Cref{alg:densest subgraph} for detail. The approximation guarantee can be analyzed in exactly the same way as in \Cref{sec:algo offline}. Analyzing the total update time, however, need a different argument. In particular, we use the following {\em charging argument}. 


%
%Our algorithm is described in \Cref{alg:densest subgraph}. It runs the static $2$-approximation $O(m)$-time algorithm of Charikar \cite{Charikar00}, denoted by {\sc StaticAlgo}, as a subroutine. 
%%
%It maintains a partition of edges in $G$ into $k$ sets denoted by $E_1, E_2, \ldots, E_k$ and computes $\sigma_i$ as the $2$-approximate value of $\sigma^*(G_i)$ in each subgraph $G_i=(V, E_i)$. When a set of new edges, denoted by $E'$, is inserted into $G$, it has to put edges in $E'$ to some $E_i$. The crucial idea is to define $i$ as the smallest value such that $|E'\cup E_1\cup \ldots \cup E_i|\leq \frac{m'}{(p')^{1-i/k}}$, where $m'$ and $q'$ are the current number of edges and insertions, respectively. The algorithm then moves all edges in $E'\cup E_1\cup \ldots \cup E_{i-1}$ to $E_i$ and recompute the value $\sigma_i$. It then uses $\max_{i=1}^k \sigma_i$ as the approximate value of $\sigma^*(G)$. 

%This means that the value of $\sigma_1$ must be updated. However, it will do so only if $|E_1$ is small enough -- in particular, if $|E_1\leq \frac{m'}{(p')^{1-1/k}}$ where $m'$ is the current number of edges in $G$ and $p'$ is the current number of edge insertions. If this is not the case, it will move all edges in $E_1$ to $E_2$. This again means that we have to update the value of $\sigma_2$. Similar to the case of $E_1$, we will do this only if $|E_2\leq \frac{m'}{(p')^{1-2/k}}$ and otherwise we will move all edges in $E_2$ to $E_3$. In general, when it has to update the value of $\sigma_i$, it does so only if $|E_i\leq \frac{m'}{(p')^{1-i/k}}$ and otherwise it moves all edges in $E_i$ to $E_{i+1}$. 


%\paragraph{Time Complexity} The running time of our algorithm depends on how much time we spend to update $E_i$ and recompute $\sigma_i$ as in Lines \ref{line:move edges} and \ref{line:recompute sigma_i} of \Cref{alg:densest subgraph}. This requires time linear in the size of $E_i$. We prove that this contributes $O(mkp^{1/k})$ total update time using the following charging argument: 
%
%Consider when we recompute $\sigma_i$ as in Line~\ref{line:recompute sigma_i}. This means that the running time to execute Line~\ref{line:recompute sigma_i} is $O(|E_i|)$. 
%

Recall that we only need to bound the total time to recompute all $\sigma_i$ (i.e. total time to execute Line \ref{line:recompute sigma_i}) since the time to execute other steps of the update operation is dominated by this. Also recall that we need $O(|E_i|)$ time each time we recompute $\sigma_i$ in Line \ref{line:recompute sigma_i}. 
%
Every time we have to execute Line \ref{line:recompute sigma_i}, we will {\em charge} this $O(|E_i|)$ cost to edges in $E'\cup E_1\cup E_2\cup \ldots \cup E_{i-1}$. 
%
In other words, for every edge $e$ and $1\leq i\leq k$, we define $\phi(e)$ to be the total charge edge $e$ received from executing Line \ref{line:recompute sigma_i} for $E_i$. Initially, $\phi_i(e)=0$ for all $i$ and $e$. When we execute Line \ref{line:recompute sigma_i} for set $E_i$, we will increase the value of $\phi_i(e)$ for every edge $e\in E'\cup E_1\cup E_2\cup \ldots \cup E_{i-1}$ by the amount of
\[\frac{|E_i|}{|E'\cup E_1\cup E_2\cup \ldots \cup E_{i-1}|\,.}
\]
(Note that when we execute Line \ref{line:recompute sigma_i}, sets $E_1, \ldots,  E_{i-1}$ are not yet set to $\emptyset$.) Now, by the definition of $i$, we know that 
\begin{itemize}
\item $|E_i|\leq m'/(p')^{1-i/k}$, and 
\item $|E_1\cup E_2\cup \ldots \cup E_{i-1}|> m'/(p')^{1-(i-1)/k}$. 
\end{itemize}

Thus, each edge will be charged by at most
\[O\left(\frac{m'/(p')^{1-i/k}}{m'/(p')^{1-(i-1)/k}}\right) =O((p')^{1/k}) = O(p^{1/k})\,.\]
Additionally, note that each edge is charged such cost from updating $E_i$ and computing $\sigma_i$ {\em at most once} 
since it will be moved from $E'\cup E_1\cup \ldots E_{i-1}$ to $E_i$ after we compute $\sigma_i$. In other words, 
$$\phi_i(e) = O(p^{1/k})$$
for all $i$ and $e$. 
%
Thus, the total update time charged over all $m$ edges is 
$$\sum_{e\in E} \sum_{i=1}^k \phi_i(e) = O(mkp^{1/k})$$ 
as desired.  




\subsection{Achieving Worst-Case Update Time}\label{sec:worst case}


Given that we can now achieve an $O(kmp^{1/k})$ total update time, which implies an $O(km/p^{1-1/k})$ amortized update time, it is natural to ask whether the same update time can be achieved {\em in the worst case}. That is, we want to get an answer with a good approximation guarantee within $O(km/p^{1-1/k})$ after we insert a set of edges. 

It is not hard to see that achieving this in the general case is quite impossible. Consider, for example, when we start with an empty graph and in the first insertion there are $m/2$ edges inserted followed by $m/2$ insertions, each with one edge (thus $p=1+m/2$). Intuitively, approximating $\sigma^*(G)$ after the first insertion will need to read the newly inserted edges and take $\Omega(m)$ time. This is far from the amortized time of $O(km^{1/k})$ achieved by our algorithm. 
%
In general, consider when there is a sequence of insertions where there are $x_i$ edges in the $i^{th}$ insertion. Then, it is intuitive that any algorithm will need $\Omega(x_i)$ time on the $i^{th}$ insertion before it can approximate the densest subgraph and process the next insertion. Our algorithm achieves almost this: it needs $O(x_ikm^{1/k})$ time on the $i^{th}$ insertion before it can gives an approximate value of the densest subgraph and start processing the $(i+1)^{th}$ insertion.

%it guarantees that if the $(i+1)^{th}$ insertion happens $\Omega(x_ikm^{1/k})$ time after the $i^{th}$ insertion, then 



%In other words, we should wait for $\Omega(x_i)$ before processing the $(i+1)^{th}$ insertion. 

% OPEN PROBLEM: Approximate in sublinear time? 



%However, in the special case where we start from an empty graph and edges are gradually inserted, i.e. $|E'|=1$ (and thus $p=m$), we can turn the $O(km^{1+1/k})$ amortized update time into a worst-case update time. ... TO DO ...

\begin{theorem}\label{thm:worst case}
For any $k\geq 1$, there is an algorithm that takes an insertion of $x$ edges and after $O(xkm^{1/k})$ time it will give a $(4k)$-approximate value of the densest subgraph of the new graph and be ready to process the next insertion. 
% After this much time, 
% in the worst case and outputs a $(2k)$-approximate value of the densest subgraph.
%a sequence of insertions 
\end{theorem}

In fact, the above theorem easily follows from its special case where $x=1$ as follows. 

\begin{lemma}\label{thm:worst case one edge}
For any $k\geq 1$, there is an algorithm that takes an insertion of an edge and after $O(km^{1/k})$ time it will give a $(4k)$-approximate value of the densest subgraph of the new graph and be ready to process the next insertion. 
\end{lemma}

\Cref{thm:worst case} follows from \Cref{thm:worst case one edge} because we can process $x$ edges in  $O(xm^{1/k})$ time by processing one edge at a time and spending $O(m^{1/k})$ time for each edge. 
%
Note that \Cref{thm:worst case one edge} gives the worst case running time that matches the amortized update time guaranteed by \Cref{thm:near linear algo}. 
%
Also note one important point of this algorithm: The algorithm might {\em not} stops its computation in $O(km^{1/k})$ time after an edge insertion; however, it will already be able to give  a $(2k)$-approximate value of the densest subgraph at that time and is ready to execute another edge insertion. 

%Our algorithm is a slight modification of \Cref{alg:densest subgraph}. We need this modification since \Cref{alg:densest subgraph} may ...

%the algorithm may still be running to find a better answer but 


\begin{algorithm}
\caption{{\sc Worst-Case-Densest-Subgraph}($G$, $k$)}\label{alg:worst case}

{\bf Input:}  The initial graph $G=(V, E)$ and an integer $k\geq 1$.

{\bf Maintain:} A $(4k)$-approximate value of $\sigma^*(G)$.

\medskip{\sc Initialize}($G$): Same as \Cref{alg:densest subgraph}.
%\begin{algorithmic}[1]
%\State $p'=0$ and $m'=|E|$.
%\State For all $1\leq i\leq k$, let $E_1=E_2=\ldots=E_{k-1} = \emptyset$,  and $\sigma_1=\sigma_2=\ldots=\sigma_{k-1}=0$. 
%\State Let $E_k=E$ and compute $\sigma_k$ as the $2$-approximate value of $\sigma(G)$ using {\sc KS-Algorithm}.
%\algstore{myalg}
%\end{algorithmic}

\medskip
{\sc Update}($E'$): When an edge $e$ is added, do the following.

\begin{algorithmic}[1]
\State $p'=p'+1$ and $m'=m'+1$.
\State $E_1=E_1\cup \{e\}$.
\State Compute $\sigma_1$ as a $2$-approximation of $\sigma^*(G_1)$.
\State For all $i\geq 2$, continue the computation of $\sigma_i$ for $m^{1/k}$ more steps. \label{line:concurrent}
\For{$i=k-1, k-2, \ldots, 1$}
\If{$|E_i|=m^{i/k}$ and the computation of $\sigma_i$ finishes}
\State $E_{i+1}=E_{i+1}\cup E_i$
\State $E_i=\emptyset$
\State $\sigma_{i+1}=\max(\sigma_i, \sigma_{i+1})$\label{line:compute sigma}
\State Initiate the computation of $\sigma_{i+1}$ as a $2$-approximation of $\sigma^*(G_{i+1})$.
(The value of $\sigma_{i+1}$ remains the same until the computation finishes.)
\EndIf
\EndFor
\end{algorithmic}

\medskip
{\sc Query}: Same as \Cref{alg:simple,alg:densest subgraph}.

%\begin{algorithmic}[1]
%\State Output $\max_{i=1}^k \sigma_i$ as the approximate value of $\sigma^*(G)$. 
%\end{algorithmic}
\end{algorithm}


Our algorithm is described in \Cref{alg:worst case}. The main idea is that it will compute the value of $\sigma_i$ {\em concurrently}. In particular, after every insertion, we will spend $O(m^{1/k})$ time to compute each $\sigma_i$. An important observation is the following. 
\danupon{The proof is still sketchy.}

\begin{observation}
The computation of $\sigma_i$ finishes before new edges are added to $E_i$.
\end{observation}
\begin{proof}
Since $|E_i|\leq m^{i/k}$, we need $O(m^{i/k})$ time to compute $\sigma_i$. The computation of $\sigma_i$ is initiated when we set $E_{i-1}=\emptyset$. Thus, there will be at least $m^{(i-1)/k}$ edge insertions before $|E_{i-1}|=m^{(i-1)/k}$ and edges in $E_{i-1}$ are added to $E_i$. Since we $O(m^{1/k})$ time per each insertion, we will have $O(m^{i/k})$ time to finish computing $\sigma_i$ before edges in $E_{i-1}$ are added to $E_i$.
\end{proof}


It follows that when we set $\sigma_i=\max(\sigma_{i-1}, \sigma_i)$ it is a $4$-approximate value of $\max(\sigma^*(G_{i-1}), \sigma^*(G_i))$ (since $\sigma_{i-1}$ and $\sigma_i$ are $2$-approximate values of $\sigma^*(G_{i-1})$ and $\sigma^*(G_i)$ respectively). Thus, while we do not finish computing the new value of $\sigma_i$ after we move edges in $E_{i-1}$ to $E_i$, the current value of $\sigma_i$ is a $4$-approximate value of $\sigma^*(G_i)$. It follows by the same analysis as in \Cref{alg:simple} that $\max_{i=1}^k \sigma_i$ is a $(4k)$-approximate value of $\sigma^*(G)$. 
%
Since we spend $O(m^{1/k})$ time to compute each $\sigma_i$ after each insertion, the algorithm needs $O(km^{1/k})$ time after each insertion as claimed. 

%{\bf Remark:} The computation of $\sigma_i$ must be done {\em concurrently}. 


%One important point: Might not finish computation ...

%
%\subsection{Generalization}\label{sec:generalization}
%
%{\bf TO FINISH OR REMOVE}
%
%\begin{theorem}[Generalization]
%If there is an $\alpha$-approximation $O(m^a n^b)$-time algorithm for the densest subgraph problem, 
%then, for any $k\geq 1$, there is an algorithm that can incrementally\danupon{To define} maintain a $(k\alpha)$-approximation of the densest subgraph with $O(m^a n^b)$ preprocessing time and $O(XXX)$ worst-case update time\danupon{Define preprocessing and update time.}.
%%$O(XXX)$ total update time. 
%\end{theorem}




%Another thing that I want to mention is that we can actually generalize the algorithm to the case where we have q updates, where q is some number. Right now we use q=m but for the node-arrival model, we can use q=n instead. And for data with time stamp, we might want to see the update every day, month, etc.The running time will be O(kmq^{1/k}). 
%
%The algorithm requires just a simple modification (I have also put a comment about this in the code). We'll have k bins as before (for some parameter k). Before, we empty the i-th bin (i=1, .., k) if it has more than m^{i/k} edges. This time, we'll empty the bin if it has more than m/q^{1-i/k} edge. Observe that the (i-1)-th bin will send edges to the i-th bin only q^{1-(i-1)/k} times because it sends at least m/q^{1-(i-1)/k} edges every time. So, the total running time of the i-th bin is m/q^{1-i/k}*q^{1-(i-1)/k} = O(mq^{1/k}). 

